#include <vector>
#include <cstring>

using namespace std;

// Bellman-Ford算法应用（不是模版）
// k站中转内最便宜的航班
// 有 n 个城市通过一些航班连接。给你一个数组 flights
// 其中 flights[i] = [fromi, toi, pricei]
// 表示该航班都从城市 fromi 开始，以价格 pricei 抵达 toi。
// 现在给定所有的城市和航班，以及出发城市 src 和目的地 dst，你的任务是找到出一条最多经过 k 站中转的路线
// 使得从 src 到 dst 的 价格最便宜 ，并返回该价格。 如果不存在这样的路线，则输出 -1。
// 测试链接 : https://leetcode.cn/problems/cheapest-flights-within-k-stops/

class Solution 
{
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) 
    {
        const int INF = 0x3f3f3f3f;
        int cur[n];
        memset(cur, 0x3f, sizeof(cur));
        cur[src] = 0;
        for(int i = 0; i <= k; ++i)
        {
            int next[n];
            // cur 是一张老表，利用这张表使松弛操作和中转次数对应起来
            memcpy(next, cur, sizeof(cur));
            bool flag = false; // 记录本轮是否产生松弛操作
            for(auto& edge : flights)
            {
                // cur[edge[0]] != INF 这说明，本轮有机会去松弛点 edge[1]
                // 当 cur[edge[0]] == INF 时，next[edge[1]] > cur[edge[0]] 肯定小于 INF
                // 所以将其删掉就等到了解法二的模样了
                if(cur[edge[0]] != INF && next[edge[1]] > cur[edge[0]] + edge[2])
                {
                    flag = true;
                    next[edge[1]] = cur[edge[0]] + edge[2];
                }
            }
            // 本轮没有松弛操作，原点到每个点的最短距离都求出来了，直接 break（小优化）
            if(!flag) break; 
            memcpy(cur, next, sizeof(next));
        }

        return cur[dst] == INF ? -1 : cur[dst];
    }
};



class Solution 
{
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) 
    {
        const int INF = 0x3f3f3f3f;
        int cur[n];
        memset(cur, 0x3f, sizeof(cur));
        cur[src] = 0;
        for(int i = 0; i <= k; ++i)
        {
            int next[n];
            memcpy(next, cur, sizeof(cur));
            bool flag = false; // 记录本轮是否产生松弛操作
            for(auto& flight : flights)
            {
                int x = flight[0];
                int y = flight[1];
                int w = flight[2];
                if(next[y] > cur[x] + w)
                {
                    flag = true;
                    next[y] = cur[x] + w;
                }
            }
            if(!flag) break; // 本轮没有松弛操作，原点到每个点的最短距离都求出来了
            memcpy(cur, next, sizeof(next));
        }

        return cur[dst] == INF ? -1 : cur[dst];
    }
};